package main

import "fmt"

//# link: https://leetcode-cn.com/problems/longest-increasing-subsequence
func main() {
	nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
	fmt.Println(lengthOfLIS(nums))
}

//给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
//子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
func lengthOfLIS(nums []int) int {
	//dp用来表示 以nums[i]结尾的子序列最大长度 ，初始值都为1
	numsLen, result := len(nums), 0
	dp := make([]int, numsLen)
	//遍历数组长度 dp[i]=前面最长子序列与当前值的最长子序列加1的长度比较
	for i := 0; i < numsLen; i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		result = max(result, dp[i])
	}
	return result
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
